package two.chapter_3.c3_1;

import two.chapter_1.c1_3.CollectionEmptyException;
import two.chapter_1.c1_3.LinkedQueue;
import two.chapter_1.c1_3.Queue;

/**
 * 基于二分查找的有序符号表
 * @param <Key>
 * @param <Value>
 */
public class BinarySearchST<Key extends Comparable<Key>,Value> implements SeqST<Key,Value> {

    private Key[] keys;
    private Value[] vals;
    private static final int DEFAULT_CAPACITY=20;

    private int size;
    public BinarySearchST(int capacity){
        keys= (Key[]) new Comparable[capacity];
        vals= (Value[]) new Object[capacity];
    }
    public BinarySearchST(){
        this(DEFAULT_CAPACITY);
    }
    @Override
    public Key min() {
        checkEmpty();
        return keys[0];
    }

    @Override
    public Key max() {
        checkEmpty();
        return keys[size-1];
    }

    /**
     * 返回小于等于指定key的最大key
     *
     * 如果key存在于符号表中，那么floor返回的是本身
     * 如果key不存在与符号表中，那么floor返回小于指定key的最大key
     *
     * @param key
     * @return
     */
    @Override
    public Key floor(Key key) {
        checkEmpty();
        int i=rank(key);
        if (i<size && key.compareTo(keys[i])==0){
            return key;
        }
        if (i==0){
            return null;
        }
        return select(i-1);
    }
    /**
     * 返回大于等于指定key的最小key
     * @param key
     * @return
     */
    @Override
    public Key ceiling(Key key) {
        int i=rank(key);
        if (i==size)return null;
        return select(i);
    }
    private void checkEmpty(){
        if (isEmpty()){
            throw new CollectionEmptyException();
        }
    }

    /**
     * 二分查找
     * @param key
     * @return
     */
    @Override
    public int rank(Key key) {
        return rank(key,0,size-1);


    }

    /**
     * 循环条件需要小于等于
     * 这样结束时lo>hi
     * 比如 1  3   5   7  9
     * rank(6）返回值是 7的索引即3
     * @param key
     * @param lo
     * @param hi
     * @return
     */
    private int rank(Key key, int lo, int hi) {

        while (lo<=hi){
            int mid=lo+(hi-lo)/2;
            int cmp=key.compareTo(keys[mid]);
            if(cmp<0){
                hi=mid-1;
            }else if (cmp>0){
                lo=mid+1;
            }else return mid;
        }
        return lo;
    }

    @Override
    public Key select(int k) {
        return keys[k];
    }

    @Override
    public void deleteMin() {
      delete(min());
    }

    @Override
    public void deleteMax() {
        delete(max());
    }

    @Override
    public int size(Key lo, Key hi) {
        if (lo.compareTo(hi)>0) return 0;
        if (contains(hi)){
            return rank(hi)-rank(lo)+1;
        } else{
            return rank(hi)-rank(lo);
        }

    }

    @Override
    public Iterable<Key> keys(Key lo, Key hi) {
        Queue<Key> queue=new LinkedQueue<>();
        for (int i=rank(lo);i<rank(hi);i++){
            queue.enqueue(keys[i]);
        }
        return queue;
    }

    /**
     * 不允许有重复元素
     *
     * @param key
     * @param value
     */
    @Override
    public void put(Key key, Value value) {
        int i=rank(key);
        if (i<size && keys[i].compareTo(key)==0){
            vals[i]=value;//更新
            return;
        }
        //不存在键为key的值，将i之后的元素向后移动一个位置
        for (int j=size;j>i;j--){
            keys[j]=keys[j-1];
            vals[j]=vals[j-1];
        }
        //存入第i个位置
        keys[i]=key;
        vals[i]=value;
        size++;
    }

    @Override
    public Value get(Key key) {
        int i=rank(key);
        if (i<size && keys[i].compareTo(key)==0){
            return vals[i];
        }
        return null;
    }

    @Override
    public void delete(Key key) {
        if (contains(key)){
            int i=rank(key);
            for (int j=i;j<size-1;j++){
                keys[j]=keys[j+1];
                vals[j]=vals[j+1];
            }
            size--;
            keys[size]=null;
            vals[size]=null;
        }

    }

    @Override
    public boolean contains(Key key) {

        return get(key)!=null;
    }

    @Override
    public boolean isEmpty() {
        return size()==0;
    }

    @Override
    public int size() {
        return size(keys[0],keys[size-1]);
    }

    @Override
    public Iterable<Key> keys() {

        return keys(keys[0],keys[size-1]);
    }
}
